package org.myy.learn.hot.动态规划;

import java.util.Arrays;

public class 零钱兑换 {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];  //i元在下标i+1处
        //for(int i=0; i<=amount; i++){dp[i] = amount;}  //ToDo 赋值 amount+1
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for (int i=1; i<= amount; i++){
            for (int j=0; j<coins.length; j++){
                if (coins[j] <= i){//ToDo 可以等于吗    >>i-coins[j]
                    dp[i] = Math.min(dp[i-coins[j]]+1, dp[i]);
                }
            }
        }
        //return dp[amount+1]; //ToDo 不能是dp[amount+1]，下标是dp[amount]
        return dp[amount] > amount ? -1 : dp[amount]; //ToDo
    }
}
